Schnelle Fourier-Transformation

Die schnelle Fourier-Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der diskreten Fourier-Transformation (DFT). Mit ihr kann ein zeitdiskretes Signal in seine Frequenzanteile zerlegt und dadurch analysiert werden.

Analog gibt es für die diskrete inverse Fourier-Transformation die inverse schnelle Fourier-Transformation (IFFT). Es kommen bei der IFFT die gleichen Algorithmen, aber mit konjugierten Koeffizienten zur Anwendung.

Die FFT hat zahlreiche Anwendungen im Bereich der Ingenieurwissenschaften, der Naturwissenschaften und der angewandten Mathematik. Außerdem kommt sie in Mobilfunktechnologien wie UMTS und LTE und bei der drahtlosen Datenübertragung zum Einsatz, etwa in der WLAN-Funknetztechnik.

Die FFT gehört zu den Teile-und-herrsche-Verfahren, sodass – im Gegensatz zur direkten Berechnung – zuvor berechnete Zwischenergebnisse wiederverwendet und dadurch arithmetische Rechenoperationen eingespart werden können.

Historisch wurde die erste Form des Algorithmus 1805 von Carl Friedrich Gauß entdeckt und zur Berechnung der Flugbahnen der Asteroiden (2) Pallas und (3) Juno verwendet. Zum ersten Mal publiziert wurde eine Variante des Algorithmus von Carl Runge im Jahre 1903 und 1905. Es folgten weitere Adaptionen, beispielsweise von Irving John Good um 1960. Das heute bekannteste Verfahren der Fouriertransformation wird James Cooley und John W. Tukey zugeschrieben, die es auf der Suche nach einem Algorithmus, um Kernwaffentests in seismografischen Daten schnell und effizient aufzuspüren, entdeckten und 1965 veröffentlichten.^[1][2] Nach Cooley und Tukey hat es darüber hinaus zahlreiche weitere Verbesserungsvorschläge und Variationen gegeben, so etwa von Georg Bruun, C. M. Rader und Leo I. Bluestein.

1. ↑ Ein Algorithmus für den Weltfrieden
2. ↑ The re-discovery of the fast Fourier transform algorithm